FIG. 1 depicts a prior art technique for using a content addressable memory (CAM) array to support traffic forwarding at a network node. In an embodiment, the technique depicted in FIG. 1 implements a routing look-up. In an embodiment, a portion or field of an incoming packet is parsed out of the packet header and is then used as a key (CAM key) to search the CAM array. The CAM array is searched in parallel for a match to the key and when a match is found in the CAM array, data that is associated with the matching entry in the CAM array (associated data) is provided as an output. Typically, the associated data is used in determining the next hop of the packet. In the example of FIG. 1, the Internet Protocol destination address (dst IP) is parsed from the incoming packet and used as the key to be fed into the CAM array. When a match is found in the CAM array, an outgoing port number is output as the associated data, thereby determining the next hop of the packet.
CAM arrays are also utilized in the implementation of Access Control List (ACL) and QOS (Quality of Service) applications. In such applications, multiple fields are often parsed out of a packet header and used as a CAM key. In ACL applications, the associated data provides a deny or permit decision on forwarding a packet. In QOS applications, the associated data provides a rule on how to prioritize a packet.
Using a CAM array within a network node to support traffic forwarding provides several advantages over the use of random access memory (RAM). These advantages include, firstly, a CAM array can be searched in parallel, thereby providing faster and more efficient searching than RAM, which must be searched in series. Secondly, bits in a CAM array can be masked so that matches can be made between a key and a CAM array entry regardless of what data is located within the key at the bit locations corresponding to the masked bit space.
Despite the advantages of using a CAM array, using a CAM array to support traffic forwarding remains problematic because of the fact that specific fields must be parsed out of incoming packets for use in searching the CAM array. The parsing of specific fields in a packet requires knowledge of the packet format (that is, the protocols under which the packet was formatted). Knowledge of packet formats is obtained by processing the header fields of incoming packets. The parsing of specific fields of packet headers consumes valuable processing resources and is time intensive.
FIG. 11 depicts a prior art technique for classifying traffic at a network node. In the prior art technique, a single CAM array is searched in series with keys related to incoming packets to classify incoming packets. The technique depicted in FIG. 11 includes incoming packets 0-3, comparand unit 1110, CAM array 1120, and clock 1130. In an embodiment, the packets 0-3 are in a fixed order, with packet 0 being the first to be classified and packet 3 being the last to be classified. In an embodiment, a key is parsed out of an incoming packet, i.e., packet 0. The key is input to the comparand unit, which generates a comparand value that corresponds to the key. The comparand value is compared against all of the entries in the CAM array. Each comparison results in the classification of one packet. In an embodiment, the comparison of the comparand value against the entries in the CAM array takes more than one clock cycle. For example, in the depiction of FIG. 11, each comparison requires an average of two (2) clock cycles to be completed, as indicated by the clock 1130. Using this technique, completing the four classification operations takes eight clock cycles.
Memory interleaving is an example of a prior art implementation in which multiple memory devices are searched in real time. In the implementation of memory interleaving, memory accesses are divided among multiple memory arrays (“N” memory arrays). However, each of the N memory arrays contains only a fraction (1/N) of the entries that a single memory array would contain if only one memory array was used. Thus, the entries in each of the N memory arrays are different from one another. In prior art memory interleaving, for every N memory accesses, each access must target a different one of the N memory arrays. If any two accesses in the N accesses target the same array, a “collision” results in which one of the two accesses stalls until the first access is complete. As a result of the collision, the overall throughput achieved from memory interleaving is reduced.
In view of the limitations of the prior art, what is needed is a technique for classifying traffic that makes efficient use of each clock cycle.